#include <stdio.h>
#include <stdlib.h>
// #include <process.h>
#include <time.h>
#include "utils/AlgorithmUtil.h"

#define ARR_LENGTH(arr) sizeof(arr)/sizeof(arr[0])

void insertSort(int arr[], int size);

int main() {
    random_init();

    #define ARR_SIZE 100 

    int maxVal = ARR_SIZE * 10;
    int original[ARR_SIZE];
    int mySort[ARR_SIZE];
    int correctSort[ARR_SIZE];
    
    for (int i = 0; i < 2000; i++) 
    {
        randomArrayFill(original, ARR_SIZE, maxVal);
        copyArray(original, mySort, ARR_SIZE);
        copyArray(original, correctSort, ARR_SIZE);
        sortArray(correctSort, ARR_SIZE);

        // insert sort
        insertSort(mySort, ARR_SIZE);
        // ,,,


        int checked = checkArray(correctSort, mySort, ARR_SIZE);
        if (!checked) {
            printArray("原始数组：", original, ARR_SIZE);
            printArray("正确排序：", correctSort, ARR_SIZE);
            printArray("我的排序：", mySort, ARR_SIZE);
            printf("--------------------\n");
            break;
        }
    }

    printf("sort success\n");
    return 0;
}

/**
 * 插入排序：有点像摸牌，前边已经排好了，新牌从后往前排插入
 *  0~1 ：1位置与前边比较，前一个比自己大 往前换，直到前边<=自己 停止
 *  0~2 ：2位置与前边比较，。。。
 *  0~3 ：3位置与前边比较，。。。
 *  ...
 *
 * @param arr
 * @return
 */
void insertSort(int arr[], int size) 
{
    for (int i = 1; i < size; i++) {
        //
        for (int j = i; j > 0 && arr[j-1] > arr[j]; j--) {
            swapArray(arr, j-1, j);
        }
    }
}